package org.schat;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Description 使用回溯算法解八皇后问题
 * @Author lsh
 * @Date 2020/3/25 15:40
 **/
public class Queen {
    static List<char[][]> ans = new ArrayList<>();

    public static void main(String[] args){
        solveQueens(8);
    }

    public static void solveQueens(int n){

        //初始化棋盘
        char[][] board = new char[n][n];
        for(int i = 0; i < board.length; i++){
            char[] line = board[i];
            for(int j = 0; j < line.length; j++){
                board[i][j] = '.';
            }
        }
        backTrack(board,0);
        for(int i = 0; i < ans.size();i++){
            System.out.println("\n\n解法"+(i+1)+":");
            char[][] bd = ans.get(i);
             for(char[] line : bd){
                System.out.println(Arrays.toString(line));
            }
        }
    }

    public static void backTrack(char[][] board,int row){
        if(row == board.length){
            ans.add(createNewObj(board));
            return;
        }
        int n = board[row].length;
        for(int col = 0; col < n; col++){
            //判断是否可放置
            if(!isValid(board,row,col)) continue;
            //choose
            board[row][col] = 'Q';
            backTrack(board,row + 1);
            //unchoose
            board[row][col] = '.';
        }

    }

    //判断border[row][col]是否可以放置Q
    public static boolean isValid(char[][] board,int row,int col){
        int n = board.length;
        //检查正上方
        for(int i = 0; i < n ;i++){
            if(board[i][col] == 'Q')
                return false;
        }
        //检查右斜上方
        for (int i = row -1, j = col + 1; i >= 0 && j < n; i--,j++){
            if(board[i][j] == 'Q')
                return false;
        }
        //检查左斜上方
        for(int i = row -1, j = col -1; i >= 0 && j >= 0; i--,j--){
            if(board[i][j] == 'Q')
                return false;
        }
        //不用检查下方，
        return true;
    }

    private static char[][] createNewObj(char[][] border){
        char[][] newBorder = new char[border.length][border.length];
        for(int i = 0; i < border.length;i++){
            char[] line =  border[i];
            for(int j = 0; j < line.length; j++){
                newBorder[i][j] = border[i][j];
            }
        }
        return newBorder;
    }
}
